Polygons are one of the basic primitives used in graphics to display surfaces on a display screen. Filled areas of polygons are especially useful in rendering surfaces of three-dimensional objects in a graphics display. In general, polygons are defined as a closed series of connected lines that may have any shape, either convex or concave. They can be filled on a display screen by activating the pixels of the display which fall on and inside the edges of a polygon. The pixels inside the edges are called interior pixels. FIG. 17 illustrates several polygons and the pixels activated to render the filled polygons.
Several techniques are used to determine which pixels should be activated to fill a polygon. These techniques are referred to as fill scan conversions. Generally, these techniques operate between a set of edges on a span, where a span is either a horizontal or a vertical row of pixels. In FIG. 17 for example, the beginning and the end of each horizontal span for each polygon are marked by darker shaded pixels. A fill scan converter may generate the pixel data within a span incrementally by stepping from pixel to pixel, for example in the X direction in FIG. 17 and calculating parameter values for each pixel. A new span may then be selected for pixel generation by stepping down one pixel row in the Y direction, and repeating the pixel-to-pixel stepping for the new span.
As may be seen from FIG. 17, the polygons may be complex. For complex polygons, such as many-sided, self-intersecting, and concave polygons, the scan conversion may be very complicated. Therefore, it may be desirable to optimize a fill scan converter to fill triangles, and then render the polygons as combinations of triangles. Additionally, since quadrilaterals are commonly found in graphic databases, it may be desirable to optimize the fill scan converter to support a quadrilateral that has been divided into two triangles. The triangle fill scan converter can then fill both of the resulting triangles.
Although FIG. 17 is depicted in two dimensions and a single color, polygons may also have color, for example as defined by red, green, and blue color values. A polygon may be three-dimensional, and therefore will have a depth associated with each pixel, normally defined as a coordinate on a Z-axis. Accordingly, the individual pixels shown in FIG. 17 may actually have an X coordinate and a Y coordinate, as well as red, green, blue, and Z-axis coordinates.
Hardware and software designed for efficient display of triangles may be divided into a number of blocks, for example a geometry accelerator block and a fill scan converter block. In such an arrangement, the geometry accelerator generates plane equations from the data for the vertices (V0, V1, V2) of a triangle. These plane equations, which uniquely define the values of the parameters associated with each pixel in a triangle, may be designed so that The fill scan converter is simple high-speed electronic hardware, which generates the pixels by "stepping" the plane equations provided by the geometry accelerator. For example, the geometry accelerator may perform additions, multiplications, and divisions, while the fill scan converter performs only additions.
When a quadrilateral is to be generated and filled, it can be divided into two separate triangles, and then the data for each triangle may be input separately to the geometry accelerator to generate the appropriate plane equations. However, this approach can use a substantial amount of processing resources, and may require lengthy calculations. It is desirable to reduce the processing resources and time required for filling a quadrilateral.
Moreover, a fill scan converter may be designed to be more efficient if provided with triangle information that is sorted with respect to vertex designation. Although sorting of vertices may be performed prior to plane equation generation, this approach uses additional processing resources and time. It is therefore desirable to reduce the processing resources and time required in generating plane equations with sorted triangle vertices.